#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<stack>
#include<string>
using namespace std;

namespace lh
{
    //https://leetcode.cn/problems/min-stack/
    //最小栈
    class MinStack {
    public:
        //初始化列表，自定义类型调用他的构造函数。MinStack()可要可不要
        MinStack() {

        }

        void push(int val) {
            _st.push(val);
            if (_minst.empty() || val <= _minst.top())
            {
                _minst.push(val);
            }
        }

        void pop() {
            if (_st.top() == _minst.top())
            {
                _minst.pop();
            }

            _st.pop();
        }

        int top() {
            return _st.top();
        }

        int getMin() {
            return _minst.top();
        }

    private:
        stack<int> _st;
        stack<int> _minst;
    };
    void test1()
    {
        MinStack minstack;
        minstack.push(-2);
        minstack.push(0);
        minstack.push(-3);
        cout << minstack.getMin() << endl;
        minstack.pop();
        cout << minstack.top() << endl;
        cout << minstack.getMin() << endl;
    }

    //https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
    //栈的压入、弹出序列
    class Solution {
    public:
        bool IsPopOrder(vector<int> pushV, vector<int> popV) {
            stack<int> st;
            int i = 0, j = 0;
            int sz = pushV.size();

            for (int i = 0; i < sz; i++)
            {
                st.push(pushV[i]);
                //连续出,栈顶和出栈序列一致则出,否则跳出继续入栈
                while (!st.empty() && st.top() == popV[j])
                {
                    j++;
                    st.pop();
                }
            }
            return st.empty();
        }
    };
    void test2()
    {
        vector<int>pushV;
        vector<int>popV;
        pushV.push_back(1);
        pushV.push_back(2);
        pushV.push_back(3);
        pushV.push_back(4);
        pushV.push_back(5);


        popV.push_back(4);
        popV.push_back(5);
        popV.push_back(3);
        popV.push_back(2);
        popV.push_back(1);

        cout << Solution().IsPopOrder(pushV, popV) << endl;
    }

    //https://leetcode.cn/problems/evaluate-reverse-polish-notation/
    //逆波兰表达式求值
    class Solution2 {
    public:
        int evalRPN(vector<string>& tokens) {
            stack<int> st;
            for (auto& str : tokens)
            {
                if (str == "+" || str == "-" || str == "*" || str == "/")
                {
                    //先弹出右值
                    int right = st.top();
                    st.pop();
                    int left = st.top();
                    st.pop();

                    switch (str[0])
                    {
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right);
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        st.push(left / right);
                        break;
                    }

                }
                else
                {
                    st.push(stoi(str));
                }
            }
            return st.top();
        }
    };
    void test3()
    {
        vector<string>tokens;
        tokens.push_back("2");
        tokens.push_back("1");
        tokens.push_back("+");
        tokens.push_back("3");
        tokens.push_back("*");

        cout << Solution2().evalRPN(tokens) << endl;
       
        tokens.clear();
        tokens.push_back("4");
        tokens.push_back("13");
        tokens.push_back("5");
        tokens.push_back("/");
        tokens.push_back("+");
        cout << Solution2().evalRPN(tokens) << endl;

    }
}


int main()
{
    cout << "第一题:最小栈" << endl;
    lh::test1();
    cout << "第二题:压入弹出序列" << endl;
    lh::test2();
    cout << "第三题:逆波兰表达式求值" << endl;
    lh::test3();
    return 0;
}